package main

import (
	"fmt"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func produceATree() TreeNode {
	/*
			3
			/ \
		   9  20
			 /  \
			15   7
	*/
	return TreeNode{
		Val: 3,
		Left: &TreeNode{
			Val:   9,
			Left:  nil,
			Right: nil,
		},
		Right: &TreeNode{
			Val: 20,
			Left: &TreeNode{
				Val:   15,
				Left:  nil,
				Right: nil,
			},
			Right: &TreeNode{
				Val:   7,
				Left:  nil,
				Right: nil,
			},
		},
	}
}
func produceATree2() TreeNode {
	/*
		          1
		         /
		        2
		       / \
		      4   5
			 /   /
		    5   4
	*/
	return TreeNode{
		Val: 1,
		Left: &TreeNode{
			Val: 2,
			Left: &TreeNode{
				Val: 4,
				Left: &TreeNode{
					Val:   5,
					Left:  nil,
					Right: nil,
				},
				Right: nil,
			},
			Right: &TreeNode{
				Val: 5,
				Left: &TreeNode{
					Val:   4,
					Left:  nil,
					Right: nil,
				},
				Right: nil,
			},
		},
		Right: nil,
	}
}

var res = 0
var depth = 0

func traverse(root *TreeNode) {
	if root == nil {
		return
	}
	depth++
	if root.Left == nil && root.Right == nil {
		if res < depth {
			res = depth
		}
	}

	traverse(root.Left)
	traverse(root.Right)

	depth--
}

func maxDepth(root *TreeNode) int {
	res = 0
	depth = 0
	traverse(root)
	return res
}
func maxDepth2(root *TreeNode) int {
	if root == nil {
		return 0
	}
	leftMax := maxDepth2(root.Left)
	RightMax := maxDepth2(root.Right)

	res := RightMax
	if leftMax > RightMax {
		res = leftMax
	}

	return res + 1
}

// ===========================================================================
var maxDiameter = 0

func traverse2(root *TreeNode) {
	if root == nil {
		return
	}

	leftMax := maxDepth2(root.Left)
	rightMax := maxDepth2(root.Right)
	thisDiameter := leftMax + rightMax

	if thisDiameter > maxDiameter {
		maxDiameter = thisDiameter
	}

	traverse2(root.Left)
	traverse2(root.Right)
}

func diameterOfBinaryTree(root *TreeNode) int {
	maxDiameter = 0
	traverse2(root)
	return maxDiameter
}

// ===========================================================================
// 543解法2
func diameterOfBinaryTree2(root *TreeNode) int {
	maxDiameter = 0
	maxDepth3(root)
	return maxDiameter
}
func maxDepth3(root *TreeNode) int {
	if root == nil {
		return 0
	}
	leftMax := maxDepth3(root.Left)
	rightMax := maxDepth3(root.Right)

	thisDiameter := leftMax + rightMax
	if thisDiameter > maxDiameter {
		maxDiameter = thisDiameter
	}

	res := rightMax
	if leftMax > rightMax {
		res = leftMax
	}
	return res + 1
}
// ===========================================================================

func main() {
	t := produceATree()
	fmt.Println(maxDepth(&t))
	fmt.Println(maxDepth2(&t))
	fmt.Println(diameterOfBinaryTree(&t))
	fmt.Println(diameterOfBinaryTree2(&t))
	t = produceATree2()
	fmt.Println(diameterOfBinaryTree(&t))
	fmt.Println(diameterOfBinaryTree2(&t))

}
